package quickSortMediana3;

public class Quick {
	
	public int[] quicksort(int[] array, int left, int right) {
		if (left >= right)
			return array;
		
		int m = particiona(array, left, right);
		quicksort(array, left, m-1);
		quicksort(array, m+1, right);
		return array;
	} 	
	
	public int particiona(int[] array, int left, int right) {
		
		int i = left + 1;
		int j = right;
		int p = array[left];
		
		while (i <= j ){
			if (array[i] < p){
				i++;
			}
			else if ( p < array[j]){
				j--;
			}
			else {
				swap(array, i, j);
			}
			
		}
		swap(array, left, j);
		
		return j;	
	}


	private void swap(int[] array, int i, int j){
		int temporario = array[i];
		array[i] = array[j];
		array[j] = temporario;
	}
	
	public int[] quickSortMedia3(int[] array, int left, int right){
		mediaDe3(array, left, right);
		
		int i = left + 1;
		int j = right - 2;
		int p = array[right - 1];
		
		while (true){
			while (array[i] < p){
				i++;
			}
			while (p < array[j]  ){
				j--;				
			} if ( i < j ){
				swap(array, i, j);
			} else {
				break;
			}	
		}
		
		swap(array, i, right - 1);
		quicksort(array, i+1, right);
		quicksort(array, left, i-1);
		return array;
		}

	private void mediaDe3(int[] array, int left, int right){
		int center = (left + right)/2;
		if (array[center] < array[left] ){
			swap(array, center, left);
		} 
		if (array[right] < array[left]){
			swap(array, right, left);
		}
		if (array[right] < array[center]){
			swap(array, right, center);
		}
		
		swap(array, center, right-1);
	}
}